快速幂 & 矩阵运算

1 模板

注意开 long long

int qpow(int x, int y)
{
    int ans = 1;
    while (y)
    {
        if (y % 2)
            ans = (ans * x) % p;
        x = (x * x) % p;
        y /= 2;
    }
    return ans;
}

2 矩阵计算

3 示例: P1962 斐波那契数列 - 洛谷

计算斐波那契数列， $n \leq 2^{63}$
可得:

$\begin{aligned} [\begin{array}{c} F_{n} \\ F_{n + 1} \end{array}] & = A [\begin{array}{c} F_{n - 1} \\ F_{n} \end{array}] = A^{2} [\begin{array}{c} F_{n - 2} \\ F_{n - 1} \end{array}] = . . . & = A^{n - 1} [\begin{array}{c} F_{1} \\ F_{2} \end{array}] = A^{n - 1} [\begin{array}{c} 1 \\ 1 \end{array}] \end{aligned}$ , $A = [\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]$

#define int long long
const int maxn = 15, mod = 1e9 + 7;
struct Matrix {
    int n, m;
    int v[maxn][maxn] = {};
    Matrix(int n, int m) :n(n), m(m) {}
    Matrix operator* (const Matrix B) const {
        Matrix C(n, B.m);
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= B.m;j++)
                for (int k = 1;k <= m;k++)
                    C.v[i][j] += v[i][k] * B.v[k][j], C.v[i][j] %= mod;
        return C;
    }
    // void print() {//输出该矩阵，用来测试 
    //     for (int i = 1;i <= n;i++)
    //         for (int j = 1;j <= m;j++)
    //             cout << v[i][j] << " \n"[i == m];
    // }
};
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;cin >> n;
    if (n <= 2) {
        cout << "1\n";return 0;
    }
    Matrix A(2, 1), B(2, 2);
    A.v[1][1] = A.v[2][1] = 1;
    B.v[1][2] = B.v[2][1] = B.v[2][2] = 1;

    auto qpow = [&](int b) {
        while (b) {
            if (b & 1) A = B * A;
            B = B * B;b >>= 1;
        }
        };
    qpow(n - 2);
    cout << A.v[2][1] << '\n';
}

4 练习: P1939 矩阵加速（数列） - 洛谷

已知一个数列 $a$ ，它满足：

a_{x} = {\begin{cases} 1 & x \in {1, 2, 3} \\ a_{x - 1} + a_{x - 3} & x \geq 4 \end{cases}

求 $a$ 数列的第 $n$ 项对 $10^{9} + 7$ 取余的值。

对于 $100 %$ 的数据 $1 \leq T \leq 100$ ， $1 \leq n \leq 2 \times 10^{9}$ 。

找出 $A$ 矩阵即可。不一样的地方是 $A$ 矩阵是 3 维的。

5 练习： ../../ACMExercises/Luogu/B3646 数列前缀和 3 - 洛谷

链接